Linear Data Structure iii Stack

Posted on | Edited on | In | | Views:

线性数据结构(三) 栈
Stack 是一种后进先出的数据结构(FILO), 基本的操作有 push(), pop(), peek(), size() 和 isEmpty().

因为它只能从一边进出, 所以是倒序的操作.所以可能想到的应用场景应该是各种对于顺序的操作. 以及相邻两个元素进行对比. 虽然它的操作很简单, 但是根据进栈和出栈的顺序不同, 可以得出不同的结果.

1
2
3
4
5
6
7
8
9
10
栈内元素: 1, 2, 3
出栈的顺序可能有:
				  3, 2, 1;
				  1, 2, 3;
				  2, 3, 1;
				  2, 1, 3;
				  1, 3, 2;
唯一不可能是情况是312, 因为如果3 已经进栈了,
那么就意味着 1 和 2 已经进(过)栈了.
而1 比 2 先进栈, 不可能比2先出栈.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

For example:

Deque stack = new ArrayDeque();

Java 中 stack 的实现通常会使用 Deque 这个 interface, 而不再使用 Stack 这个类了. 具体原因:

  • 对于最新的 Java framework 来说, Stack 的线程安全显得太冗余.
  • 通过 LinkedList 和 ArrayList 实现的 Deque 可以实现 Deque 和 Stack 的各种增删改查功能. 这样使得数据结构的整合更加统一, 使用 generic 类型来创建对象也更符合 Java OOP 的设计理念.
  • 最后 LinkedList 和 ArrayList 都不是 Synchronized, 所以开销更小.

使用 Deque 接口:

operation FistElement Last Element
return type exception null Exception null
insert addFirst offerFirst addLast offerLast
remove removeFirst pollFirst removeLast removeFirst
examine getFirst peekFirst getLast peekLast

代码实现:

使用 LinkedList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class MyStackLL<E> {
	private static class ListNode<E> {
	    public E val;
	    public ListNode next;
	    public ListNode(E val) {
	        this.val = val;
	        this.next = null;
		  }
	}

    private ListNode head;
    private int size;

    public MyStackLL(){
        head = null;
    }

    public void push(E e){
        ListNode<E> node = new ListNode(e);
        node.next = head;
        head = node;
        size++;
    }

    public E pop(){
        if (head == null) {
            return null;
        }
        ListNode<E> node = head;
        head = head.next;
        node.next = null;
        size--;
        return node.val;
    }

    public Object peek() {
        if (head == null) {
            return null;
        } else {
            return head.val;
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

使用 Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class MyStackAL<E> {

  private Object[] array;
  private static final int CAP = 16;
  private static final int SCALE_FACTOR = 2;
  int top;
  int size;
  public MyStackAL() {
      array = new Object[CAP];
      top = -1;
  }

  public void push(E e) {
      if (top == array.length - 1) {
          array = Arrays.copyOf(array, CAP * SCALE_FACTOR);
      }
      array[++top] = e;
      size++;
  }

  public Object pop() {
      if (top < 0) {
          return null;
      }
      Object res = array[top--];
      size--;
      return res;
  }

  public Object peek() {
      return top < 0 ? null : array[top];
  }

  public int size() {
      return size;
  }

  public boolean isEmpty() {
      return size == 0;
  }
}

所有操作的时间复杂度均为 O(1), 使用 array 的扩容方法 amortize 的时间复杂度依然是 O(1).

because the initial capacity is n. At the time we need to extend the capacity of the stack, it takes O(n) to copy the elements, and push operation will take O(1) for the upcoming n elements. When we add up the time of copy and adding, the average time complexity for each of upcoming elements will be O(n) + O(n) / n = O(2). Thus the amortized time complexity is O(1).